// 子集：如果集合A的任意元素都是集合S的元素，则称集合A是集合S的子集
// 给定一个集合S，枚举其所有可能的子集

// 这里介绍一个枚举子集的方法，二进制枚举子集算法
// 思路：对于元素个数为n的集合S，每个元素都有选取和未选取两种状态，我们用1表示选取该元素，用0表示不选取该元素
// 这样我们可以用长度为n的二进制数来表示集合S或者表示S的子集，其中二进制的每一位数都对应了集合中某一个元素的选取状态
// 对于长度为5的集合S，我们只需要从00000-11111枚举一次，即可得到长度为5的集合的所有子集
// 对于长度为n的集合S，只需要枚举2的n次，即可得到所有子集

function subSets(S) {
    let n = S.length
    let result = []
    for (let i = 0; i < 1 << n; i++) {
        let arr = []
        // 按位与1取与，如果是1的话，放入arr
        for (let j = 0; j < n; j++) {
            if (i >> j & 1) {
                arr.push(S[j])
            }            
        }
        result.push(arr)        
    }
    return result
}

let arr = [1, 2, 3, 5]
console.log(subSets(arr));